{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Validate Binary Search Tree\n",
    "\n",
    "[原题](https://mp.weixin.qq.com/s/gXUQKt4Q42dFzVRxNeFHng)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "You are given the root of a binary search tree. Return true if it is a valid binary search tree, and false otherwise.\n",
    "\n",
    "> **Tips**: A binary search tree has the property that all values in the left subtree must less than or equal to the root and all values in the right subtree must greater than or equal to the root.\n",
    "\n",
    "The binary tree shown below is a search tree.\n",
    "\n",
    "```text\n",
    "#      5\n",
    "#    /   \\\n",
    "#   3     7\n",
    "#  / \\   /\n",
    "# 1   4 6\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "''' The Class Definition '''\n",
    "class TreeNode:\n",
    "    def __init__(self, key):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.key = key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "''' Main Algorithm '''\n",
    "def is_bst(root):\n",
    "    # Make a flag to record if the current binary tree is validate.\n",
    "    flag = True\n",
    "\n",
    "    # If current root has no left subtree,\n",
    "    # it also has no need to check it.\n",
    "    if root.left is not None:\n",
    "        # If the left subtree isn't a binary search tree\n",
    "        # or its root is larger than the current root,\n",
    "        # the current tree can't be a binary search tree.\n",
    "        if not is_bst(root.left) or root.left.key > root.key:\n",
    "            flag = False\n",
    "\n",
    "    # The same as the right subtree.\n",
    "    if root.right is not None:\n",
    "        if not is_bst(root.right) or root.right.key < root.key:\n",
    "            flag = False\n",
    "\n",
    "    # Report the flag\n",
    "    return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "''' Main Scripts '''\n",
    "a = TreeNode(5)\n",
    "a.left = TreeNode(3)\n",
    "a.right = TreeNode(7)\n",
    "a.left.left = TreeNode(1)\n",
    "a.left.right = TreeNode(4)\n",
    "a.right.left = TreeNode(6)\n",
    "print(is_bst(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notes\n",
    "\n",
    "A binary tree isn't a validate search tree only when ...\n",
    "\n",
    "1. one of its subtree isn't a validate search tree.\n",
    "2. the value of the left-child is greater than that of the root.\n",
    "3. the value of the right-child is less than that of the root."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
